//请判断一个链表是否为回文链表。 
//
// 示例 1: 
//
// 输入: 1->2
//输出: false 
//
// 示例 2: 
//
// 输入: 1->2->2->1
//输出: true
// 
//
// 进阶： 
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 链表 双指针

package leetcode.editor.cn;

public class PalindromeLinkedList2 {
    public static void main(String[] args) {
        Solution solution = new PalindromeLinkedList2().new Solution();
        ListNode listNode = ListNodeUtil.constructList(new int[]{1, 0,1});
        System.out.println(solution.isPalindrome(listNode));
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode p = head;
        int count = 0;

        while (p != null) {
            p = p.next;
            count++;
        }



        int[] array = new int[count];
        p = head;
        int i = 0;
        while (p != null) {
            array[i++] = p.val;
            p = p.next;
        }

        int headIndex = 0;
        int tailIndex = i - 1;
        for (; headIndex <= tailIndex; headIndex++,tailIndex--) {
            int left = array[headIndex];
            int right = array[tailIndex];

            if (left != right) {
                return false;
            }
        }

        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}